package com.now.presum;

/**
 * 304. 二维区域和检索 - 矩阵不可变
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 *
 * 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
 * 实现 NumMatrix 类：
 *
 * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
 *
 */
public class NumMatrix {
  int[][] preSum;
  public NumMatrix(int[][] matrix) {

    int rowNum = matrix.length, colNum = matrix[0].length;
    preSum=new int[rowNum+1][colNum+1];
    for(int i=1;i<=rowNum;i++){
      for(int j=1;j<=colNum;j++){
        // 从坐标(0,0)开始算起，矩阵的和为上一行同列的矩阵和preSum[i-1][j]
        // +同行上一列的矩阵和preSum[i][j-1]
        // -上一行上一列的矩阵和preSum[i-1][j-1]
        // + 当前格matrix[i - 1][j - 1] ，因为是从[1，1]开始填的，实际原矩阵里的当前值为preSum[i-1][j-1]
        preSum[i][j]=  preSum[i-1][j] + preSum[i][j-1] + matrix[i
            - 1][j - 1] - preSum[i-1][j-1];
      }
    }
  }

  /**
   * 当前矩阵里的值之和为 右下角坐标的和preSum[row2+1][col2+1]
   * - 右下角的行左上角的列对应到(0,0)坐标的矩阵和preSum[row2+1][col1]
   * - 右下角的列左上角的行对应到(0,0)坐标的矩阵和preSum[row1][col2+1]
   * + 减了两次的左上角矩阵和 preSum[row1][col1]
   *
   * @param row1
   * @param col1
   * @param row2
   * @param col2
   * @return
   */
  public int sumRegion(int row1, int col1, int row2, int col2) {
    return preSum[row2+1][col2+1]-preSum[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];
  }

  public static void main(String[] args) {
    int[][] matrix = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
    NumMatrix numMatrix = new NumMatrix(matrix);
    System.out.println(numMatrix.sumRegion(2, 1, 4, 3));
    System.out.println(numMatrix.sumRegion(1, 1, 2, 2));
    System.out.println(numMatrix.sumRegion(1, 2, 2, 4));
  }
}
